#! /usr/bin/env python

# Alunos:   Eliezer de Souza da Silva  RA: 124065
#           Fernanda Brandao Silva     RA: 060727
#           Michel Silva Fornaciali    RA: 071884
# IA368R: Eduardo Valle - Trabalho 2, Programa 5

import sys
import numpy as np
from scipy.spatial.distance import cdist

def getResults(dist, files, n):
    # recupera os n resultados mais relevantes
    
    for i in range(n):
        v = np.argmin(dist)     # recupera o resultado da base que apresentou a distancia minima
        sys.stdout.write(files[v]+ " " + str(dist[v])+"\n")
        dist[v] = np.inf        # altera a distancia minima para Infinito, para que essa imagem nao seja fornecida como resultado novamente
    
                	
def getData(filename):
# le histogramas de cada imagem da base

        # os elementos de indice 'i' das listas files, hist correspondem a informacoes de uma mesma imagem
        files = []      # lista de arquivos de imagens da base
        
	fid = open(filename, 'r')
	lines = fid.readlines()
	
	# para cada linha do arquivo, separa os dados: nome e histograma da imagem
	n = len(lines[0].split())
	m = len(lines) 
        base = np.zeros((m,n-1)) # vetor de histogramas - cada linha da matriz 'base' corresponde a um histograma da base
        
	for i in range(m):
                sl =  lines[i].split()
                files.append(sl[0])
		base[i,:] = np.array(sl[1:n], dtype=float) 

	return files, base
	
	
	
def main():
    
	filename = sys.argv[1]  # codebook de histogramas
	n = int(sys.argv[2])    # numero de resultados relevantes
	
	files, base = getData(filename)
	
	strHist = sys.stdin.read().split()               # string do histograma de consulta
	hist = np.array(strHist,dtype=float)      # converte string do histograma em um vetor
	
	# calculo da distancia de manhattan entre os histogramas da base e o histograma de consulta
        dist = np.sum(abs(base - hist), axis=1)
        
        getResults(dist,files, n) # recupera os resultados mais relevantes para a consulta
	
	
if __name__ == "__main__":
	main()